#pragma once
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

class TrieTree
{
public:
	TrieTree()
	{
		trie.push_back({});
		IsEnd.push_back(0);
		Id = 0;
	}

	bool insert(string& s)
	{
		int p = 0;
		for (auto ch : s)
		{
			if (!trie[p].count(ch))
			{
				trie[p][ch] = ++Id;
				trie.push_back({});
				IsEnd.push_back(0);
			}

			p = trie[p][ch];
		}

		if (IsEnd[p])
		{
			return false;
		}
		IsEnd[p]++;
		return true;
	}

	int find(string& s)
	{
		int p = 0;
		for (auto ch : s)
		{
			if (!trie[p].count(ch))
			{
				return 0;
			}
			p = trie[p][ch];
		}

		return IsEnd[p];
	}

private:
	vector<unordered_map<char,int>> trie;
	vector<int> IsEnd;
	int Id;
};

